package A一周刷爆LeetCode.A基础班.F二叉树;

import java.util.LinkedList;

/**
 * @author wei.zhao
 * @description: 判断一颗二叉树是否是完全二叉树
 * @date 2022年02月24日 10:53
 */
public class Code07_IsCBT {

    public static void main(String[] args) {
        Node head = new Node(7);
        head.left = new Node(5);
        head.right = new Node(9);
        head.left.left = new Node(4);
        head.left.right = new Node(6);
        head.right.left = new Node(8);
        head.right.right = new Node(10);
        head.right.right.right = new Node(11);
        System.out.println("是否是完全二叉树：" + isCBT(head));
    }

    public static boolean isCBT(Node head) {
        LinkedList<Node> list = new LinkedList<>();
        list.add(head);
        boolean hasBoth = true;
        while (!list.isEmpty()) {
            Node node = list.pop();
            if ((node.left == null && node.right != null) || (!hasBoth && (node.left != null || node.right != null))) {
                return false;
            }
            if (node.right == null) {
                hasBoth = false;
            }
            if (node.left != null) {
                list.add(node.left);
            }
            if (node.right != null) {
                list.add(node.right);
            }
        }
        return true;
    }

}
